//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
// Related Topics 贪心 字符串 排序 👍 370 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;

public class BaShuZuPaiChengZuiXiaoDeShuLcof {
    public static void main(String[] args) {
        int[] nums = {3,3,3,0,3001};
        new BaShuZuPaiChengZuiXiaoDeShuLcof().new Solution().minNumber(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 这个排序规则我真是，看了题解豁然开朗
         * 先将数字都转换成字符串
         * 排序时将字符串进行拼接 if x+y > y+x 则x排在后边，即x>y
         */
        public String minNumber(int[] nums) {
            StringBuilder s = new StringBuilder();
            String[] strings = new String[nums.length];
            for (int i = 0; i < nums.length; i++) strings[i] = String.valueOf(nums[i]);// 转化为字符串
            // compare方法调用后返回值 >= 0 的话说明a > b
            Arrays.sort(strings, (a, b) -> ((a + b).compareTo(b + a)));
            for (String s1 : strings) s.append(s1);
            return s.toString();
        }

        public void quickSort(String[] strings, int left, int right){
            if (left >= right) return;
            int l = left, r = right;
            //快排选取最左边作为哨兵
            String temp = strings[left];
            while (l < r){
                while ((strings[r] + strings[left]).compareTo(strings[left] + strings[r]) >= 0 && l < r) r--;
                while ((strings[l] + strings[left]).compareTo(strings[l] + strings[left]) <= 0 && l < r) l++;
                temp = strings[l];
                strings[l] = strings[r];
                strings[r] = temp;
            }
            strings[l] = strings[left];
            strings[left] = temp;
            quickSort(strings, l + 1, right);
            quickSort(strings,left, r-1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}